package SortAlgorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;

/**
 * @description: 跳表
 * @author: 小白白
 * @create: 2021-12-25
 **/

public class SkipList {

    /**
     * (1) 由很多层结构组成，level是通过一定的概率随机产生的；
     * (2) 每一层都是一个有序的链表，默认是升序 ；
     * (3) 最底层(Level 1)的链表包含所有元素；
     * (4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现；
     * (5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
     */

    private static final float SKIPLIST_P = 0.5f;
    private static final int MAX_LEVEL = 16;
    private int levelCount = 1;
    // 满层头节点
    private Node head = new Node(MAX_LEVEL, -1);


    /**
     * 查找
     */
    public Integer find(int value) {
        Node p = this.head;
        // 从最高层开始找
        for (int i = this.levelCount - 1; i >= 0; --i) {
            // 向右找
            while (p.topNext[i] != null && p.topNext[i].val < value) {
                p = p.topNext[i];
            }
            // for循环: 向下找
        }
        // 找到了第一个小于目标元素的节点p了
        // 最终一定会到最底层的节点, 因为for即使找到了,也会一直往下循环
        // 下一个元素不为null(value大于表内所有元素的情况) && 判断下一个元素是否为目标元素即可
        if (p.topNext[0] != null && p.topNext[0].val == value) {
            // 找到了
            return p.topNext[0].val;
        } else {
            // 不存在此节点
            return null;
        }
    }

    /**
     * 插入的时候就维护了索引，每次经过对应的层级的时候就插入对应的索引，直到到达原链表
     */
    public void insert(int value) {
        // 随机获取索引级别
        int level = this.randomLevel();
        Node newNode = new Node(level, value);
        // 新节点的父节点(即插入操作完成后的父节点)
        Node[] newNode_parentNode = new Node[level];

        // 每一层的起始节点都是头节点, 所以不管从哪一层开始, 都是从head开始遍历搜索
        Node p = this.head;
        for (int i = level - 1; i >= 0; --i) {
            // 能否向右走?
            while (p.topNext[i] != null && p.topNext[i].val < value) {
                // 向右走
                p = p.topNext[i];
            }
            // 找到当前层的父节点了
            newNode_parentNode[i] = p;
            // for循环: 当前遍历的节点往下走
        }

        // 更新新节点的每层索引
        for (int i = 0; i < level; ++i) {
            newNode.topNext[i] = newNode_parentNode[i].topNext[i];
            newNode_parentNode[i].topNext[i] = newNode;
        }

        // 更新最大层高
        if (this.levelCount < level) {
            this.levelCount = level;
        }
    }

    /**
     * 删除
     */
    public void delete(int value) {
        Node[] deleteNode_parentNode = new Node[this.levelCount];

        Node p = this.head;
        // 从最高层开始
        for (int i = this.levelCount - 1; i >= 0; --i) {
            // 向右
            while (p.topNext[i] != null && p.topNext[i].val < value) {
                p = p.topNext[i];
            }
            // 记录当前层的parentNode
            deleteNode_parentNode[i] = p;
            // for循环: 向下
        }

        // 同查找, 保证表内有此元素
        if (p.topNext[0] == null || p.topNext[0].val != value) {
            return;
        }

        for (int i = this.levelCount - 1; i >= 0; --i) {
            // parentNode不为null且下一个节点等于value, 则删除此节点
            if (deleteNode_parentNode[i].topNext[i] != null && deleteNode_parentNode[i].topNext[i].val == value) {
                deleteNode_parentNode[i].topNext[i] = deleteNode_parentNode[i].topNext[i].topNext[i];
            }
        }
        // 特殊情况: 顶层索引只有一个值, 且将其删除了, 那么就是 最高层的下一个元素 == null, 就需要将全局层次降低。
        // 即使不操作也不会影响最终结果, 这里是为了提高效率,避免遍历无效层次。
        while (this.levelCount > 1 && this.head.topNext[this.levelCount] == null) {
            this.levelCount--;
        }

    }

    private int randomLevel() {
        int level = 1;
        // Math.random()范围[0~1); 到达n层的概率是 (0.5^n), [50%, 25%, 12.5%...]
        while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
            level += 1;
        return level;
    }

    // 链表节点对象
    public class Node {
        private Integer val = null;
        // 当前节点多层索引数组, [i]表示第i层索引指向的下一个节点, i就是上下层, [i]就是当前level的下一个节点
        private Node[] topNext;

        public Node(int level) {
            this.topNext = new Node[level];
        }

        public Node(int level, Integer val) {
            this.topNext = new Node[level];
            this.val = val;
        }

        public Integer getVal() {
            return this.val;
        }

        public void setVal(Integer val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        Random random = new Random();
        List<Integer> list = new ArrayList<>(100000);
        for (int i = 0; i < 100000; i++) {
            list.add(random.nextInt(300000));
        }
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            skipList.insert(list.get(i));
        }
        System.out.println((System.currentTimeMillis() - startTime) / 1000);
        TreeSet<Integer> treeSet = new TreeSet<>();
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            treeSet.add(list.get(i));
        }
        System.out.println((System.currentTimeMillis() - startTime) / 1000);
        int num = -1;
        for (int i = 0; i < 100; i++) {
            num = random.nextInt(300000);
            startTime = System.currentTimeMillis();
            skipList.find(num);
            System.out.println(System.currentTimeMillis() - startTime);
        }
        for (int i = 0; i < 100; i++) {
            num = random.nextInt(300000);
            startTime = System.currentTimeMillis();
            treeSet.contains(num);
            System.out.println(System.currentTimeMillis() - startTime);
        }
    }

}